package 力扣;

import javax.sound.midi.Soundbank;

/**
 * @author yyq
 * @create 2022-06-16 15:06
 */
public class bag01 {
    public static void main(String[] args) {
        bag01 bag01=new bag01();
        bag01.printDP(new int[]{1,3,4},new int[]{15,20,30},4);
    }
    //每个物品只有一个
    void printDP(int[] weight,int[] value,int bag){
        // dp[i][j]: 选择前ｉ个物品装入背包重量为ｊ的最大价值
        int[][] dp=new int[weight.length][bag+1];
        // 初始化dp数组 需要初始化第一行和第一列
        for (int i=0;i<dp.length;i++){
            dp[i][0]=0;
        }
        for (int j=1;j<=bag;j++){
            if(weight[0]<=j)
                dp[0][j]=value[0];
            else dp[0][j]=0;
        }
        // 完善dp数组
        for (int i=1;i<dp.length;i++){
            for (int j=1;j<=bag;j++){
                if(weight[i]>j){
                    dp[i][j] = dp[i-1][j];
                }else {
                    dp[i][j] = Math.max(value[i]+dp[i-1][j-weight[i]],dp[i-1][j]);
                }
            }
        }
        for (int i=0;i<dp.length;i++){
            for (int j=0;j<=bag;j++) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }
    }
}
